package main

// 560. 和为 K 的子数组
func main() {
	nums := []int{1, 2, 3}
	k := 3
	res := subArraySum(nums, k)
	println(res)
}

func subArraySum(nums []int, k int) int {
	// 前缀和, 最优版本
	res := 0
	prefixMap := make(map[int]int)
	prefixMap[0] = 1
	preSum := 0
	for _, n := range nums {
		preSum += n
		res += prefixMap[preSum-k]
		prefixMap[preSum]++
	}
	return res
}

func subArraySum2(nums []int, k int) int {
	// 前缀和, 双循环版本
	prefixSumArray := make([]int, len(nums)+1)

	prefixSumArray[0] = 0
	for idx, num := range nums {
		prefixSumArray[idx+1] = prefixSumArray[idx] + num
	}

	res := 0
	for idx := 0; idx <= len(nums); idx++ {
		for i := idx; i >= 0; i-- {
			if prefixSumArray[idx]-prefixSumArray[i] == k {
				res++
			}
		}
	}

	return res
}

// 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
//
//子数组是数组中元素的连续非空序列。
//
//示例 1：
//
//输入：nums = [1,1,1], k = 2
//输出：2
//示例 2：
//
//输入：nums = [1,2,3], k = 3
//输出：2
//
//提示：
//
//1 <= nums.length <= 2 * 104
//-1000 <= nums[i] <= 1000
//-107 <= k <= 107
